/*================================================================
*   Copyright (C) 2024 baichao All rights reserved.
*
*   文件名称：main.c
*   创 建 者：baichao
*   创建日期：2024年04月25日
*   描    述：
*
================================================================*/

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct Node {
  int val;
  struct Node* next;
  struct Node* random;
};

struct Node* copyRandomList(struct Node* head) {
  if (head == NULL) {
    return NULL;
  }

  // 在每个节点后面创建一个新节点
  struct Node* curr = head;
  while (curr != NULL) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->val = curr->val;
    newNode->next = curr->next;
    newNode->random = NULL;

    curr->next = newNode;
    curr = newNode->next;
  }

  // 复制random指针
  curr = head;
  while (curr != NULL) {
    if (curr->random != NULL) {
      curr->next->random = curr->random->next;
    }
    curr = curr->next->next;
  }

  // 拆分链表
  struct Node* newHead = head->next;
  struct Node* prev = head;
  curr = head->next;
  while (curr != NULL) {
    prev->next = curr->next;
    prev = curr;
    curr = curr->next;
    if (curr != NULL) {
      prev->next = curr->next;
    }
  }

  return newHead;
}

int main() {
  struct Node* currNode = NULL;
  struct Node* head = (struct Node*)malloc(sizeof(struct Node));

  head->val = 7;
  head->next = (struct Node*)malloc(sizeof(struct Node));
  currNode = head->next;

  currNode->val = 13;
  currNode->next = (struct Node*)malloc(sizeof(struct Node));
  currNode = currNode->next;

  currNode->val = 11;
  currNode->next = (struct Node*)malloc(sizeof(struct Node));
  currNode = currNode->next;

  currNode->val = 10;
  currNode->next = (struct Node*)malloc(sizeof(struct Node));
  currNode = currNode->next;

  currNode->val = 1;
  currNode->next = (struct Node*)malloc(sizeof(struct Node));
  currNode = NULL;

  head->random = NULL;
  head->next->random = head;
  head->next->next->random = head->next->next->next->next;
  head->next->next->next->random = head->next;
  head->next->next->next->next->random = head;

  copyRandomList(head);

  return 0;
}
